package listbyorder.access001_100.test57;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/2 8:49
 */
public class Solution1 {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        // 将元素复制到新的数组中进行求解
        int[][] newArr = Arrays.copyOf(intervals, intervals.length + 1);
        newArr[intervals.length] = newInterval;
        return merger(newArr);
    }

    private int[][] merger(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        Stack<Integer> stack = new Stack<>();
        int[] temp = new int[2];
        for (int i = 0; i < intervals.length; i++) {
            temp = intervals[i];
            if (stack.isEmpty() || temp[0] > stack.peek()) {
                stack.push(temp[0]);
                stack.push((temp[1]));
            } else {
                stack.push(Math.max(stack.pop(), temp[1]));
            }
        }
        int[][] res = new int[stack.size() / 2][2];
        int i = res.length - 1;
        while (!stack.isEmpty()) {
            res[i][1] = stack.pop();
            res[i][0] = stack.pop();
            i--;
        }
        return res;
    }
}
